"""
This is E.G.W.'s entry into the 'hunger games' contest.
It keeps a high reputation for as long as possible, and then tries to convert the reputation into food right before the game ends,
    so that whatever damage it does by slacking will be done to genuine rivals and not to players destined to be eliminated early.
"""

need_to_init = True
num_opponents = 0
num_actions = 0
my_earnings = 0
my_hunts = 0
my_slacks = 0
world_food = 0
world_earnings = -1
world_anarchy = False
unpunished_crime_profits = 0
sim_reputation = 0.0
sim_hunts = 0
sim_slacks = 0

def hunt_choices(round_number, current_food, current_reputation, m, player_reputations):
    
    """ Step 1: Import global variables. """
    
    global need_to_init
    global num_opponents
    global num_actions
    global my_earnings
    global my_hunts
    global my_slacks
    global world_earnings
    global world_anarchy
    global unpunished_crime_profits
    global sim_reputation
    global sim_slacks
    global sim_hunts
    
    """ Step 2: Initialize if necessary.
                (Count number of opponents, begin tracking world food supply.)
            Check whether number of opponents has changed.
                (If so, there's no stabilization emergency.) """
    
    if need_to_init:
        need_to_init = False
        num_opponents = len(player_reputations)
        world_food = current_food * (1 + num_opponents)
    elif (num_opponents != len(player_reputations)):
        world_earnings = -1
        num_opponents = len(player_reputations)
    
    """ Step 3: Construct hunt_decisions and a list of indexes. """
    
    hunt_decisions = list()
    index = list()
    for i in range(0,num_opponents):
        hunt_decisions.append('h')
        index.append(i)
    
    """ Step 4: Sort the list of indices.
            (I'm using a standard bubble sort algorithm; not super-efficient, but should be good enough.) """
            
    if (num_opponents > 1):
        bubbled = True
        while bubbled:
            bubbled = False
            for n in range(0,num_opponents-1):
                i = index[n]
                j = index[n+1]
                if (player_reputations[i] > player_reputations[j]):
                    index[n] = j
                    index[n+1] = i
                    bubbled = True

    """ Step 5: Simulate a baseline strategy.
            Here's an extremely simple and yet reasonably powerful strategy that somebody or other is bound to use:
            
                def hunt_choices(round_number, current_food, current_reputation, m, player_reputations):
                    hunt_decisions = list()
                    for r in player_reputations:
                        if (r < current_reputation):
                            hunt_decisions.append('s')
                        else:
                            hunt_decisions.append('h')
                    return hunt_decisions
            
            I'm not going to use that strategy, but I _am_ going to keep track of what it would be doing, for purposes of setting a reputation baseline.
                If someone's reputation is lower than its reputation, that proves that they're attacking people who don't deserve it.
                I'll assume that anybody whose reputation is higher than the sim's to be a 'cop' with whom I should try to cooperate,
                    and anybody whose reputation is worse than the sim's to be a 'robber' whom I should try to exterminate.
                And of course, I'll be sure to keep my own reputation no lower than the sim's,
                    so that I won't be attacked by people who are running it.
        
        By the way, I'm also going to do a check here to see whether there's anybody else with a reputation near my own. """
    
    num_cops = 1
    num_robbers = 0
    
    low_anon_threshold = my_hunts / (num_actions + (num_opponents/2) + 0.5)
    high_anon_threshold = (my_hunts + (num_opponents/2) + 0.5) / (num_actions + (num_opponents/2) + 0.5)
    anonymity = False
    
    for r in player_reputations:
        if (r < sim_reputation):
            sim_slacks += 1
            num_robbers += 1
        else:
            sim_hunts += 1
            num_cops += 1
        
        if ((low_anon_threshold <= r) and (r <= high_anon_threshold)):
            anonymity = True
    
    """ Step 6: Throw a tantrum if appropriate.
            If I've got only one opponent, or if I'm about to die, or if I've decided that mutual cooperation is impossible, I slack against everyone.
            In the single-opponent case, the only way he can win is if he already had more food than I did
                --and if he doesn't waste it trying to entice me into cooperating with him.
                Of course, this strategy ensures that one of us won't survive; but I'm playing to win and don't care about an 'I survived' t-shirt. """
    
    if ((num_opponents <= 1) or (current_food + my_earnings <= 0) or (world_anarchy)):
        for i in range(0,num_opponents):
            hunt_decisions[i] = 's'
            my_slacks += 1
    else:
    
        """ Step 7: Slack only when necessary.
                The plan is to conserve my reputation as long as possible, converting it to food only when there's some pressing need to do so.
                That way I'll tend to have a relatively high reputation for most of the game, hopefully lowering the odds of people targeting me,
                    and when I _do_ start slacking I'll be doing it against finalists rather than people who die early. """
    
        my_slacks_this_round = 0
    
        """ Case 7a: Crime should not pay.
                If someone has a low reputation and seems not to mind, that's a problem; my strategy is predicated on the assumption that a high reputation will be valuable.
                So I need to see to it that indiscriminate slacking is a losing strategy.
                
                I assume that any punishments I dole out have been or will be echoed by the other 'cops', so each punishment I do can be expected to cause (3 * num_cops) pain to the criminals.
                We don't have to punish criminals very quickly, as long as we punish them faster than they can commit crimes.
                    The maximum profit per round a criminal can get from crimes, if he attacks all of his opponents at once, is (num_opponents + 3):
                        "num_opponents" because the robber saves 1 unit of food in each interaction (spending 2 and getting 0 rather than spending 6 and getting 3)
                        "+ 3" because each crime costs the victim 3 units of food, so if the robber victimizes everybody then he's raised his relative standing by 3.
                I dole out punishments to the lowest-reputation players available, but only those whom the sim identified as 'robbers';
                    'cops' reputations are potentially due solely to punishing robbers rather than to committing 'crimes' themselves. """

        if (num_robbers > 0):
            punishments_needed = 1 + ((num_robbers * (num_opponents + 3)) / (3 * num_cops))
            n = 0
            while ((n < num_opponents) and (my_slacks + my_slacks_this_round < sim_slacks-1) and (my_slacks_this_round < punishments_needed) and (unpunished_crime_profits > 0)):
                i = index[n]
                if (player_reputations[i] < sim_reputation):
                    hunt_decisions[i] = 's'
                    my_slacks_this_round += 1
                    unpunished_crime_profits -= 3 * num_cops
                n += 1
                
        """ Case 7b: The nail that sticks up gets hammered.
                If I find myself in the happy position of being the highest-reputation player, it's probably time to do some extra slacking, to avoid standing out.
                    Under these circumstances, I will slack against the highest-reputation players,
                        on the theory that if having a high reputation weren't working well for me, I'd already have spent my reputation on something else.
                    I'll slack until I'm tied for highest-reputation.
                        If I'm still above the sim at that point, as well as above at least one actual player, I'll then slack to one step below the highest.
                If I'm not the highest-reputation player, I slack against a single random target who is higher-reputation than me.
                    This might not be strictly necessary, but anyone whose reputation is higher than mine probably isn't doing his share of punishing criminals,
                        and maybe this will help wake him up.
                    I only do this if I think I'm anonymous; if he's using some tit-for-tat type strategy, I wouldn't want to make him target me.
                    I also only do it if there are criminals available for him to try to punish. """
                
        n = num_opponents-1
        i = index[n]
        if (current_reputation >= player_reputations[i]):
            extra_slacks = my_hunts - (player_reputations[i] * num_actions)
            j = index[0]
            if ((my_slacks + my_slacks_this_round + extra_slacks < sim_slacks) and (player_reputations[j] < player_reputations[i])):
                extra_slacks += 1
            while ((n >= 0) and (extra_slacks > 0)):
                i = index[n]
                if (hunt_decisions[i] == 'h'):
                    hunt_decisions[i] = 's'
                    my_slacks_this_round += 1
                    extra_slacks -= 1
                n -= 1
        elif ((anonymity) and (num_robbers > 0) and (my_slacks + my_slacks_this_round < sim_slacks-1)):
            i = 0
            go = True
            while ((i < num_opponents) and (go)):
                if ((hunt_decisions[i] == 'h') and (player_reputations[i] > current_reputation)):
                    hunt_decisions[i] = 's'
                    my_slacks_this_round += 1
                    go = False
                i += 1
        
        """ Case 7c: Unfair equilibrium.
                If it's after round 1025 and the world food supply has stabilized, but some players have lower reputation than me, that's a bad situation;
                    those players might win just by virtue of having slacked more, even if they've been slacked against no less often than I have.
                    (Why "1025"?  Well, I admit, it's rather arbitrary, but here's my thinking:
                        Even the people with the worst strategies aren't going to start dying until round 300 or so;
                           they started with 300 food per interaction, and if every interaction they have with somebody involves mutual slacking,
                               then they're losing 2 food per interaction.  But some of the time--call it half--they get that food back due to the bonus.
                        So someone like me who wants to be sure his slacks get targeted against genuine rivals, rather than against opponents who die early,
                            will plan to change their behavior sometime after round 300.
                        But he shouldn't put it off too long, lest the tournament program decide that the situation has stabilized, and shut down the tournament.
                        So he'll pick some number a little bit higher than 300.  e.g. "500", "666", "911", "1000", or "1024".
                        If several algorithm change their behavior on 1024, and several others change theirs on 1025 in reaction, that could break the equilibrium.
                        But if the equilibrium hasn't broken by 1025, I begin to doubt that it will ever break.)
                Under these circumstances, I start slacking against the highest-reputation players whose reputations are nevertheless lower than mine,
                    on the theory that they're less likely than the lowest-reputation players to have been targeted earlier.
                (I'm still not willing to drop my reputation below the sim's, though,
                    since the food supply might be stable because a bunch of people are playing the sim's strategy,
                    and dropping below that strategy might cause them to decide to stop hunting with me.) """
        
        if ((world_earnings >= 0) and (round_number > 1025) and (my_slacks + my_slacks_this_round < sim_slacks)):
            while ((n >= 0) and (my_slacks + my_slacks_this_round < sim_slacks)):
                i = index[n]
                if ((player_reputations[i] < current_reputation) and (hunt_decisions[i] == 'h')):
                    hunt_decisions[i] = 's'
                    my_slacks_this_round += 1
                n -= 1
        
        """ Case 7d: Threat of starvation.
                I don't intend to die with a reputation higher than the sim's.
                So if I'm approaching a 'use it or lose it' situation with a higher reputation than that, it's time to start converting some of that reputation into food.
                To estimate how many slacks I'll be able to use in the future, I first estimate how many turns are left to me by looking at current trends.
                    Then I multiply by num_cops, which is equal to num_opponents (the number of people I can slack against per round) minus num_robbers (the number of people the sim slacks against per round).
                Under these circumstances, I slack against random targets. """
        
        if (my_earnings < 0):
            future_slacks = ((current_food-1) / (0-my_earnings)) * num_cops
            i = 0
            while ((i < num_opponents) and (my_slacks + my_slacks_this_round < sim_slacks - future_slacks)):
                if (hunt_decisions[i] == 'h'):
                    hunt_decisions[i] = 's'
                    my_slacks_this_round += 1
                i += 1

        """ Step 8: Clean up. """
        
        my_slacks += my_slacks_this_round
        my_hunts += num_opponents - my_slacks_this_round
    num_actions += num_opponents    
    sim_reputation = (sim_hunts + 0.0) / (num_actions)
    return hunt_decisions;

def hunt_outcomes(food_earnings):
    
    """ Step o1: Import global variables. """
    
    global num_opponents
    global my_earnings
    global world_anarchy
    global unpunished_crime_profits
    
    """ Step o2: Add up my earnings, and count the number of crimes committed against me.
            Assuming that on average, I'm no more likely to victimized by a crime than anyone else,
                every crime I see represents, on average, a full spree against everyone;
                that spree will have netted the criminal the full (num_opponents + 3) profit; see earlier calculation. """

    my_earnings = 0
    num_crimes = 0
    
    for e in food_earnings:
        my_earnings += e
        if (e < 0):
            num_crimes += 1
            unpunished_crime_profits += num_opponents + 3
    
    """ Step o3: Detect anarchy.
            'Anarchy' is a situation in which civilization is collapsing and it's no longer profitable to worry about reputation at all.
            If I suffer a round in which I would have done better to slack against everybody and be slacked against by everybody, I declare anarchy.
            During a declaration of anarchy, I refuse to cooperate with anyone.
            I rescind the declaration of anarchy if losing the support of my allies would be more expensive than hunting with everybody in order to maintain that support. """
    
    if (my_earnings < num_opponents*(-2)):
        world_anarchy = True
    elif (3 * (num_opponents - num_crimes) > (num_opponents + 3)):
        world_anarchy = False

def round_end(award, m, number_hunters):

    """ Step e1: Import global variables. """
    
    global num_opponents
    global my_earnings
    global world_food
    global world_earnings
    
    p_t_pmo = (num_opponents+1) * num_opponents
    
    """ Step e2: Update current estimate of world food supply.
            Each non-hunter lowered the world food supply by 2.
            If the award happened, it increased world food supply by award size times the number of people. """
    
    world_earnings = -2 * ((p_t_pmo) - number_hunters)
    world_food += world_earnings + (award * (num_opponents + 1))
    
    """ Step e3: Update projections of future food supply, based on expected future awards.
            Assuming the number of hunts stays about the same, the odds of an award in a given round are number_hunters over players-times-players-minus_one.
            World benefit if award happens is 2 times players-times-players-minus-one; so the p_t_pmo's cancel and the expected world benefit from award is 2 times number_hunters.
            My benefit from awards is 2 times players-minus-one. """

    world_earnings += 2 * number_hunters
    my_earnings += (2 * number_hunters) / (1 + num_opponents)
